{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Project: Fast Multipole Methods\n",
    "\n",
    "The purpose of this project is to implement the tree code and fast multipole\n",
    "methods for the N-body summation problem. Given $\\boldsymbol x = (x_j)\\in \\mathbb R^N, \\boldsymbol y = (y_i)\\in \\mathbb R^N$, let \n",
    "\n",
    "$$A_{i,j} = \\frac{1}{\\|x_j - y_i\\|^2}.$$ \n",
    "\n",
    "For a given vector $\\boldsymbol q \\in \\mathbb R^N$, we will compute the matrix-vector product\n",
    "\n",
    "$$\\boldsymbol u = A \\boldsymbol q$$ \n",
    "\n",
    "in $\\mathcal O(N\\log N)$ and $\\mathcal O(N)$ operations.\n",
    "\n",
    "Reference: \n",
    "\n",
    "[Fast Multipole Methods](http://math.uci.edu/~chenlong/226/FMMsimple.pdf)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Step 1: Direct Sum\n",
    "\n",
    "Generate two random vectors `x, y` with length `N`. Although the direct sum\n",
    "can be implemented in the double for loops, in MATLAB, it is better to\n",
    "generate the matrix first and then compute the matrix-vector product for\n",
    "another random vector `q`.\n",
    "\n",
    "- Use double `for` loops to generate the matrix `A`\n",
    "- Use vector product to generat `A` in one line"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Step 2: Compute the weight\n",
    "\n",
    "- Loop over cells `for i=1:N` to compute the weight\n",
    "\n",
    "- Try to remove the for loop using vectorization. \n",
    "\n",
    "The loop over levels is small (only $log N$ times) and thus can be kept. To store the weight in different levels, use `cell` structure. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Step 3: Evaluation procedure\n",
    "\n",
    "- Find the interaction list. \n",
    "- Loop over each cell in a given level and compute the far field in the interaction list. \n",
    "- In the fines level, add the near field by direct sum or matrix-vector product using a small matrix."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Step 4: Test\n",
    "\n",
    "- Choose small `N` and `J = 1`. Make sure the code works for one level (only four intervals) first by comparing the result using tree algorithm with the result in Step 1.\n",
    "\n",
    "- Test the performance for different `N` and plot the CPU time vs N for both direct method and your tree code."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Step 5 (optional): Fast Multipole Methods\n",
    "\n",
    "Modify the tree code to fast multipole methods.\n",
    "\n",
    "- Compute the weight by restriction from the fine grid to coarse grid.\n",
    "\n",
    "- Implement the `M2L`: multipole expansion to local expansion\n",
    "\n",
    "- Change the evaluation of far field in the interaction list to the merge of coefficients `b` in the local expansion.\n",
    "\n",
    "- Translate the local expansion using the prolongation operator.\n",
    "\n",
    "- Evaluate in the finest level.\n",
    "\n",
    "- Plot the CPU time vs N to confirm the `O(N)` complexity."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Matlab",
   "language": "matlab",
   "name": "matlab"
  },
  "language_info": {
   "codemirror_mode": "octave",
   "file_extension": ".m",
   "help_links": [
    {
     "text": "MetaKernel Magics",
     "url": "https://github.com/calysto/metakernel/blob/master/metakernel/magics/README.md"
    }
   ],
   "mimetype": "text/x-matlab",
   "name": "matlab",
   "version": "0.14.3"
  },
  "toc": {
   "colors": {
    "hover_highlight": "#DAA520",
    "navigate_num": "#000000",
    "navigate_text": "#333333",
    "running_highlight": "#FF0000",
    "selected_highlight": "#FFD700",
    "sidebar_border": "#EEEEEE",
    "wrapper_background": "#FFFFFF"
   },
   "moveMenuLeft": true,
   "nav_menu": {
    "height": "120px",
    "width": "252px"
   },
   "navigate_menu": true,
   "number_sections": true,
   "sideBar": true,
   "threshold": 4,
   "toc_cell": false,
   "toc_section_display": "block",
   "toc_window_display": false,
   "widenNotebook": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
